package com.LeetCode.BackTrace;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * N皇后
 */
public class EightQueue {
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.x = new int[n+1];
        res = new ArrayList<>();
        dfs(0);
        return res;

    }

    List<List<String>> res = new ArrayList<>();

    int[] x;

    int n;

    int sum = 0;

    /**
     * 第 dep 层的剪枝
     * @param dep
     */
    public void dfs(int dep){
        if(dep >= n){
            sum++;
            int[] tmp_x = x;
            res.add(buildAns(tmp_x));
            return;
        }

        for(int i = 0; i<n; i++){
            x[dep] = i;
            if(isVail(dep)) dfs(dep + 1);
        }
    }

    public boolean isVail(int index){
        for(int i = 0; i<index; i++){
            if(x[index] == x[i] || Math.abs(i - index) == Math.abs(x[i] - x[index]))
                return false;
        }
        return true;
    }

    public List<String> buildAns(int[] tmp){
        StringBuilder strb = new StringBuilder();
        List<String> ans = new ArrayList<>();
        for(int i = 0; i<tmp.length; i++){
            for(int j = 0; j<tmp[i]; j++){
                strb.append(".");
            }
            strb.append("Q");
            for(int k = tmp[i] + 1; k<tmp.length; k++){
                strb.append(".");
            }
            ans.add(strb.toString());
            strb.delete(0,strb.length());
        }
        return ans;
    }

    @Test
    public void test(){
       solveNQueens(9);
        System.out.println(sum);
    }
}
